|Title of the article||
AN EVOLUTIONARY METHOD FOR SOLVING THE PROBLEM OF THE QUADCOPTER GROUP FOR IMPROVING THE QUALITY OF AREA MONITORING
Diveev Askhat Ibragimovich, doctor of technical sciences, chief of the division of safety and nonlinear analysis, Federal research center «Computer science and control» of the Russian Academy of Sciences (Dorodniсyn Computer Center of RAS) (119333, 40 Vavilov street, Moscow, Russia); Professor of the department of Mechanics and mechatronics in RUDN University, firstname.lastname@example.org
The paper is devoted to the solution of a problem of search of optimum trajectories for monitoring of area by means of group of quadrotors. It is shown that this task comes down to a three-dimensional problem of group of travelling salesmen representatives and is NPhard and this problem doesn't have an algorithm for search solution with a polynomial speed of convergence. It is offered for the solution of this problem to use a variational genetic algorithm with small variations of exchange and an insert. The detailed description of a variation genetic algorithm for the solution of a task of group of travelling salesmen is provided. Effective use of the principle of small variations requires creation of the basic decision with the closest to optimum assessment of criterion function. For creation of the basic decision it is offered to use a greedy algorithm. In a computing experiment the problem of search of ways for four quadrotors which have to begin to undergo the movement from one point to pass in the sum two hundred points is considered, and to return back to the initial point. By means of the offered variation genetic algorithm optimum trajectories for each quadrotor are found. Total length of the found trajectories shorter in 6 times then an initial trajectory and less on 16 percent of the trajectory of the basic solution found by a greedy algorithm.
three dimensional travelling salesmen problem, group of quadrotors, variational genetic algorithm, NP-hard problem
Дата обновления: 17.01.2018 13:37